package learn.link;

import learn.CommUtil;

import java.util.HashMap;

/**
 * 一种特殊的单链表节点类描述如下
 * class Node {
 * int value;
 * Node next;
 * Node rand;
 * Node(int val) { value = val; }
 * }
 * rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。
 * 给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
 * 【要求】
 * 时间复杂度O(N)，额外空间复杂度O(1)
 */
public class CopyListWithRandom {


    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);

        head.random = head.next;
        head.next.next.random = null;
        head.next.next.next.random = head;
        head.next.next.next.next.random = head.next.next;


        printLinkedList(head);
        Node node = copyRandomList(head);
        printLinkedList(node);
    }

    public static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }


    public static Node copyRandomList(Node head) {
        //复制链表
        Node n1 = head;
        while (n1 != null) {
            Node node = new Node(n1.val);
            Node next = n1.next;
            n1.next = node;
            node.next = next;
            n1 = next;
        }
        //复制random指针
        n1 = head;
        while (n1 != null) {
            n1.next.random = n1.random == null ? null : n1.random.next;
            n1 = n1.next.next;
        }
        //分离
        n1 = head;
        Node n3 = n1.next; //新head
        while (n1 != null) {
            Node n2 = n1.next;
            n1.next = n1.next.next;
            n2.next = n2.next == null ? null : n2.next.next;
            n1 = n1.next;
        }
        return n3;
    }


    public static void printLinkedList(Node node) {
        System.out.println();
        System.out.print("Linked List: ");
        while (node != null) {
            String str = null;
            if (node.random == null) {
                str = node.val + "->null ";
            } else {
                str = node.val + "->" + node.random.val + "-(" + node.hashCode() + ") ";
            }
            System.out.print(str);
            node = node.next;
        }
        System.out.println();
    }

}
